This application makes reference to and claims all benefits accruing under 35 U.S.C. Section 119 from applications for PACKET SWITCHING APPARATUS AND METHOD IN DATA NETWORK filed earlier in the Korean Industrial Property Office on Jun. 12, 1999 and Dec. 22, 1999 and there duly assigned Serial No. 21940/1999 and 60235/1999, respectively.
1. Field of the Invention
The present invention relates to a packet switching system in a data network. More particularly, the present invention relates to an apparatus and method of switching packets in parallel.
2. Description of the Related Art
In all different types of networks, excluding a point-to-point network, there exists a device for data collection and distribution. A switch and a router are two of the best examples of such data collection and distribution devices. In general, a data collection and distribution device has at least two ports. The device receives data through at least one of the ports, performs the necessary data processing, and then outputs the processed data through one or more ports.
During the data collection, processing and distributing processes, congestion within the device occurs. This congestion causes latency in data transmission. The most important reason among other various reasons for such congestion is the time required for processing the data.
A conventional data packet processing method for a packet switching system operates according to the following steps:
Step 1: a certain port receives a data packet;
Step 2: a first-in first-out (FIFO) section temporarily stores the input data packet;
Step 3: the input data packet waits to be processed while the previously inputted data packets are processed;
Step 4: a data packet processing section performs the necessary process with respect to the input data packet stored in the FIFO;
After step 4, the data processing requires a complicated decision process and this decision requires the transfer of information between decision-making modules, i.e., a controller and an information resource.
Step 5: after the completion of the packet processing, the data packet processing section checks whether other packets previously processed exist on the corresponding output port;
Step 6: if any other previously processed packet exists, the data packet processing section stores the processed packet in a buffer; and,
Step 7: if the previously processed packets are all outputted, the data packet processing section transmits the processed packet stored in the buffer to the output port.
According to the conventional data packet processing method, since a single data packet processing section controls a plurality of ports and processes only one packet at a time, it can be easily implemented with a simple construction.
However, in the event that the number of input packets becomes greater with no change in the data processing time (actually, most packet switches and routers have this characteristic), the data line becomes an idle state. That is, data is not transmitted through the data line due to the delay problem in the data packet processing section. If the delay is particularly severe, data loss may occur which affects the integrity of the information.
Meanwhile, there are two elements, which should be considered in the packet processing. These elements are: (1) a control section for controlling and judging the whole processing procedure; and, (2) an information resource for storing and providing information required for the judgment of the control section. In most cases, the information resource is embodied in the form of a register and a memory. The reason that the conventional packet data processing method processes only one packet at a time in the packet switching system is because the information resource is provided using a single memory.
Accordingly, in order to solve the problems involved in the related art and to provide a rapid packet processing, the information that needs to be stored in the resource should be classified into sections or groups, so that the respective information groups are stored in different resources. Also, a plurality of transmission/reception control sections (more than the number of resources for the respective groups) should be allocated to reduce the processing overhead with respect to the input data packets.
Moreover, the transmission/reception control sections may be allocated for the respective ports. These transmission/reception control sections can reduce the control overhead and rapidly process the packets by simultaneously accessing the information resources for the respective groups.
Meanwhile, the transmission/reception control sections should be able to share the information resources. Accordingly, an arbiter or a scheduler should make the respective transmission/reception control section access one resource at a time. In case that the transmission/reception control sections access a specified information resource excessively, the access load should be maintained and balanced by readjusting the groups again.
FIG. 1 shows the construction of one embodiment known in the conventional packet switching apparatus. Referring to FIG. 1, a host 100 controls the whole operation of the packet switching apparatus. The host 100 takes charge of the uppermost layer and transmits commands that are inputted to the packet switching apparatus. A first MAC port 110 to the n-th MAC port 1n0 can be connected to another packet switching apparatus, router, or PC and perform a standard Medium Access Control (MAC) to output data packet transmission/reception commands to a transmission/reception control section 120. A data switching section 130 determines the paths of data and control signals to the host 100, the first MAC port 110 to the n-th MAC port 1n0, and a packet memory 150 under the control of the transmission/reception control section 120. The data switching section 130 may be implemented by a multiplexer/demultiplexer.
A search memory 140 stores information for determining an output MAC port corresponding to a destination address of the received packet, thus enables a registered MAC address to be detected. A packet memory 150 is provided with a plurality of information resources, such as an address table 152, a port table 154, and a packet descriptor 156. The packet memory 150 stores the input data packets. The address table 152 stores information on the MAC address, and the port table 154 stores status information, enable information, and information upon completion of the receiving operation. The packet descriptor 156 stores information about the respective packets (for example, packet connection information) stored in the packet memory 150.
The transmission/reception control section 120 controls the transmission/reception of packets inputted/outputted through the first MAC port 110 to the n-th MAC port 1n0 in accordance with the packet transmission/reception command. Specifically, the transmission/reception control section 120 temporarily stores the received data packet, checks whether the destination address of a header of the received packet is a registered address by accessing the search memory 140, and finds out in what position of the address table 152 the registered MAC address information is stored. Then, the transmission/reception control section 120 determines the MAC port to which the received packet is outputted.
During the packet reception, the transmission/reception control section 120 stores the received data packet in the packet memory 150 by accessing the address table 152, port table 154, and packet descriptor 156.
During the packet transmission, the transmission/reception control section 120 transmits the data packet stored in the packet memory 150 through the corresponding output port by accessing the address table 152, port table 154, and packet descriptor 156.
FIG. 2 shows the construction of another embodiment of the conventional packet switching apparatus. Referring to FIG. 2, a bus interface 212 receives a data packet from a host bus 210 and outputs the data packet to a first MAC port 211 to the n-th MAC port 21n. Similarly, the bus interface 212 outputs the data packet transmitted from the MAC ports to the host bus 210.
The first MAC port 211 to n-th MAC port 21n perform the standard MAC-control and outputs a data packet transmission/reception command to the transmission/reception control section 120. A MAC port interface 238 serves as an interface between the respective MAC ports and the transmission/reception control section 228. The MAC port interface 238 is provided with a transmission/reception FIFO for each MAC port and temporarily stores the sub packets.
A multiplexer 224 selects the corresponding data packet among the data packets for the respective ports outputted from the MAC port interface 238 and outputs the corresponding data packet to the transmission/reception control section 228. A demultiplexer 226 demultiplexes the data packet outputted from the transmission/reception control section 228 and outputs the demultiplexed data packets to the corresponding ports.
A search memory 236 stores information for determining an output MAC port corresponding to a destination address of the received packet. A packet memory 234 is provided with a plurality of information resources, such as an address table, port table, and packet descriptor. The packet memory 234 stores the input data packets.
The transmission/reception control section 228 controls the transmission/reception of the packets inputted/outputted through the first MAC port 210 to the n-th MAC port 21n in accordance with the packet transmission/reception command. Specifically, the transmission/reception control section 228 temporarily stores the received data packet, checks whether the destination address of a header of the received packet is a registered address by accessing the search memory 236, and finds out in what position of the address table (not illustrated) in the packet memory 234 the registered MAC address information is stored. Then, the transmission/reception control section 238 determines the MAC port to which the received packet is outputted.
During the packet reception, the transmission/reception control section 228 stores the received data packet in the packet memory 234 by accessing the address table, port table, and packet descriptor (not illustrated) provided in the packet memory 234.
During the packet transmission, the transmission/reception control section 228 transmits the data packet stored in the packet memory 234 through the corresponding output port by accessing the address table, port table, and packet descriptor.
According to the conventional packet switching apparatus shown in FIGS. 1 and 2, since a single transmission/reception control section receives the data packet transmission/reception commands from a plurality of ports and various different types of information resourcesxe2x80x94for example, the address table, port table, etc., are stored in a single packet memoryxe2x80x94it is necessary that only one packet be processed at a time.
Therefore, the packet delay occurs during the data packet processing, thereby causing the data line to become idle state. For instance, if the transmission/reception control section is performing a command form in a certain port, a packet from another port must wait until the performance of the command is completed.
FIG. 3 illustrates a status flowchart showing the reception control flow of the conventional packet switching system. Referring to FIGS. 1 and 3, xe2x80x9cRx Controlxe2x80x9d refers to a series of operations performed based on the information obtained after the search operation of the transmission/reception control section 120.
Specifically, FIG. 3 illustrates a series of control operations that the transmission/reception control section 120 undergoes when receiving the data packets from the first MAC port 110 to the n-th MAC port 1n0 and when storing the received data packets in the packet memory 150. FIG. 3 is the simplest state diagram, except for the case of processing various errors, address mismatch, filtering, etc. At each state shown in FIG. 3, the time required for processing the packet of 64 bytes is indicated in the event that the transmission/reception control section 120 operates at a frequency of 50 MHz. As illustrated in FIG. 3, it can be known that a plurality of control states exist from an idle state 300 to a packet transmission (Xfer_pkt) state 332.
Table 1 below represents the operations performed in the respective states shown in FIG. 3 during the reception control operation by the conventional packet switching device. Table 1 also represents the packet memory 150, address table 152, and port table 154 the transmission/reception control section 120 as they access through the data switching section 130 in the respective states. The table also indicates the data processing time in the respective states when the transmission/reception control section operates at the frequency of 50 MHz in the event of receiving the packet of 64 bytes.
As shown in Table 1, it is known in the art that according to the conventional packet switching method, the transmission/reception control section 120 requires a significant amount of time for sending/receiving information by accessing the port table 154 and the address table 152, in addition to the time required for actually storing the data packets in the packet memory 150.
Additionally, during a receiving cycle, the respective time required by the respective state for accessing the port table 154, address table 152, and packet memory 150 is summarized as follows:
In the event that the conventional packet switching apparatus of FIG. 1 is actually implemented to operate at a frequency of 50 MHz and receives data packets of 64 bytes, the time required for accessing the port table 154 is 820 nS. In total, the time required for accessing the packet memory 150 is 720 nS and the time required for accessing the address table 152 is 820 nS.
For instance, if transmission/reception control sections 120 are independently arranged for the first MAC port 110 to n-th MAC port 1n0, respectively, and the port tables for the respective MAC ports are distributed among the respective transmission/reception control sections 120, the port table access time will be greatly reduced.
In practice, the time required for the whole receive control cycle will be reduced to about 820 nS (on the basis of the access time of the address table 152).
Moreover, if the address table 152 is separated from the packet memory 150 and the respective transmission/reception control sections simultaneously access the address table 152 and/or the packet memory 150, the transmission/reception control sections of the different ports will be able to access the address table 152 and the packet memory 150 simultaneously. Accordingly, the delay of packet transmission can be reduced, and an effective data transmission can be achieved.
If the address table 152 and the transmission/reception control sections for the respective ports are built in the same chip, and the access of the address table 152 is of 32 bits or more, the time required for accessing the address table 152 will be below 820 nS. Accordingly, in the whole receive control cycle, the bottleneck will be the time (720 nS) required for accessing the packet memory. In other words, the time required for the receive control cycle will be reduced below 720 nS.
Table 2 below shows operations performed in the respective states in case that the conventional packet switching apparatus of FIG. 1 performs the transmission control.
In Table 2, the following operation can be performed in a read port table state. The transmission/reception control section 120 reads the current transmission address pointer by accessing the port table 154. If the packet to be transmitted is a start of packet (SOP), the transmission/reception control section 120 initializes the transmission byte of the port table 154 and reads a packet data pointer by accessing the packet descriptor 156. If the packet to be transmitted corresponds to a multi-cast, it reads a multi-cast data pointer.
Also, in Table 2, the following operation can be performed in the packet transmission (Xfer_pkt) state. The transmission/reception control section 120 reads the sub packet to be transmitted by accessing the packet memory 150. If the packet to be transmitted is a start of packet (SOP), the transmission/reception control section 120 dequeues a transmission buffer provided in the packet memory 150 and enqueues an empty buffer. Then, the transmission/reception control section 120 decreases the current packet count. If the current packet count is xe2x80x9c0xe2x80x9d, the transmission/reception control section 120 disables the corresponding port queue.
Meanwhile, in case that the packet switching apparatus of FIG. 1 performs the transmission control operation, the control overhead is not so big in comparison to the actual transmission operation of the data packet.
However, if the control operation and the transmission operation are separated from each other in the same manner as in the receive control operation, the time required for processing the data packet can be reduced. For instance, if the packet descriptor 156 is provided in a transmission block of the respective port transmission/reception control section, the time required for the whole transmission cycle can be reduced.
FIG. 4 is a timing diagram illustrating the case that packets are sent and received between the MAC interface and the transmission/reception control section of the conventional packet switching apparatus of FIG. 2. In FIG. 2, the size of the respective packets being transmitted/received is 64 bytes, and thus one packet becomes the SOP as well as the EOP. Also, the operating frequency is 50 MHz, and the clock frequency is {fraction (1/20 )}nS.
The transmission/reception section 228 processes the packets from a specified MAC port previously searched in the data receive state 424. In a search and transmission state 426, a search operation with respect to the packet to be processed nextxe2x80x94for instance, outputted from another MAC portxe2x80x94not the above MAC port, and an operation of transmitting the packet to be presently transmitted to the corresponding MAC port are performed. If the search and transmitting state 426 is completed, the transmission/reception control section 228 enters into the transmitting state 428 and performs the packet transmission. Then, one cycle of the packet processing terminates after the transmitting state 428 is completed. At this time, the period of the data receive state 424 is 2480 nS, and the added period of the search and transmitting state and the transmitting state is 1520 nS.
In FIG. 4, the receive (Rx) control overhead is given by:
(1xe2x88x92320/2480)=87%xe2x80x83xe2x80x83[Equation 1]
Here, xe2x80x9c2480xe2x80x9d represents the period of the data receive state 424 and xe2x80x9c320xe2x80x9d represents the time required for storing the actual receive data packet from the corresponding MAC port in the packet memory 150 by the transmission/reception control section 228.
Also, in FIG. 4, the transmission (Tx) control overhead is given by:
(1xe2x88x92320/1520)=79%xe2x80x83xe2x80x83[Equation 2]
Here, xe2x80x9c1520xe2x80x9d represents the added period of the search and transmitting state 426 and the transmitting state 428 and xe2x80x9c320xe2x80x9d represents the time required for transmitting the actual transmission data packet from the packet memory 234 to the corresponding MAC port by the transmission/reception control section 228.
Also, in FIG. 4, the total control overhead is given by:
(1xe2x88x92640/4000)=84%xe2x80x83xe2x80x83[Equation 3]
Here, xe2x80x9c4000xe2x80x9d represents the time for one cycle of the packet processing and xe2x80x9c640xe2x80x9d means the time required for transmitting the actual data packet by accessing the packet memory 234 by the transmission/reception control section 228.
From Equation 3, it can be known that if the packet size of the conventional packet switching apparatus of FIG. 2 is 64 bytes, the control overhead is 84%. Specifically, 84% of the time required for inputting, processing, and then outputting one data packet is used for the control operation and the remaining 16% is used for the actual data transmission.
Accordingly, the present invention has been made in an effort to solve the problems occurring in the related art, and one object of the present invention is to provide an apparatus for performing a high-speed packet switching by reducing a control overhead in a data network.
It is another object of the present invention to provide an apparatus which can rapidly process packets with a control overhead reduced in a data network by classifying an information resource into groups, storing the groups in a plurality of different resources, and independently accessing the information resources by a plurality of transmission/reception control sections, respectively.
It is still another object of the present invention to provide an apparatus which can rapidly process packets with a control overhead reduced in a data network by classifying an information resource into groups, storing the groups in a plurality of different resources, and independently accessing the information resources by a plurality of port transmission/reception control sections, respectively.
It is still another object of the present invention to provide an apparatus and method which can perform a high-speed packet switching in a data network by classifying information resources required for packet switching such as a packet descriptor, port table, link memory, address table, etc., into groups, and accessing in parallel the information resources by scheduling operations of a plurality of transmission/reception control sections.
In order to achieve the above objects, according to the present invention, there is provided a packet switching apparatus in a data network comprising: a plurality of ports for taking charge of an input/output of packet transmission/reception commands and data packets: a plurality of transmission/reception control sections for accessing information resources classified into groups in response to the packet transmission/reception commands and for storing the corresponding data packets in a packet memory or transmitting the corresponding data packets stored in the packet memory to the corresponding ports; a plurality of the information resources for storing in groups information required for packet switching and for providing the information stored therein to the transmission/reception control sections; and, a plurality of information resource schedulers, connected to the respective information resources, for scheduling accesses of the transmission/reception control sections.
In another aspect of the present invention, there is provided a packet switching method in a data network, comprising a first step of a plurality of transmission/reception control sections outputting corresponding access signals to schedulers of information resources classified into groups to access the respective information resources, a second step of the schedulers of the respective information resources performing a scheduling with respect to the access signals so that the plurality of transmission/reception control sections can access one of the information resources at a time, and a third step of the plurality of transmission/reception control sections storing the received data packets or transmitting the stored data packets with reference to the corresponding information resources if access paths are connected.